package redis

import (
	"crypto/md5"
	"fmt"
	"sort"
)

type position [16]byte

type node struct {
	position [16]byte
	target   string
}

type ConsistentHash struct {
	replicas         int
	targetCount      int
	nodes            []node
	target2Positions map[string][]position
}

type nodeSlice []node

func (c *ConsistentHash) sortNodes() {
	sort.Sort(nodeSlice(c.nodes))
}

func ByteArrLess(a position, b position) bool {
	len := len(a)
	for i := 0; i < len; i++ {
		if a[i] == b[i] {
			continue
		}

		return a[i] < b[i]
	}
	return false
}

func (ns nodeSlice) Swap(i, j int) {
	ns[i], ns[j] = ns[j], ns[i]
}

func (ns nodeSlice) Len() int {
	return len(ns)
}

func (ns nodeSlice) Less(i, j int) bool {
	return ByteArrLess(ns[i].position, ns[j].position)
}

func (c *ConsistentHash) addTarget(target string) bool {
	_, ok := c.target2Positions[target]
	if ok {
		return false
	}

	var tmpNode node
	positions := make([]position, c.replicas)
	for i := 0; i < c.replicas; i++ {
		s := fmt.Sprintf("%s%d", target, i)
		position := hash(s)
		positions[i] = position
		tmpNode.position = position
		tmpNode.target = target
		c.nodes = append(c.nodes, tmpNode)
	}
	c.target2Positions[target] = positions
	return true
}

func (c *ConsistentHash) AddTargets(targets []string) {
	if len(targets) == 0 {
		return
	}
	c.replicas = 1000 / len(targets)
	for _, target := range targets {
		c.addTarget(target)
	}
	c.sortNodes()
}

func (c *ConsistentHash) Lookup(k string) string {
	kHash := hash(k)
	for _, value := range c.nodes {
		if ByteArrLess(kHash, value.position) {
			return value.target
		}
	}

	return c.nodes[0].target
}

func hash(k string) position {
	return md5.Sum([]byte(k))
}
